package basic.study.leetcode;

import java.util.Arrays;
import java.util.Stack;

/**
 * @ClassName Hard84
 * @Description 柱状图中最大的矩形
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/24 16:02
 * @Version 1.0
 */
public class Hard84 {
    /**
     * 枚举高度法
     */
    static class Solution {
        public int largestRectangleArea(int[] heights) {
            int maxArea = 0;
            int area;
            for (int i = 0; i < heights.length; i++) {
                area = getArea(heights, i);
                maxArea = Math.max(area, maxArea);
            }
            return maxArea;
        }

        //假设index出取得最低
        private int getArea(int[] heights, int index) {
            int left = index;
            int right = index;

            while (left - 1 >= 0 && heights[left - 1] >= heights[index]) {
                left--;
            }
            while (right + 1 <= heights.length - 1 && heights[right + 1] >= heights[index]) {
                right++;
            }
            return (right - left +1) * heights[index];
        }
    }

    /**
     * 单调栈法，只存递增的
     */
    class Solution1 {
        public int largestRectangleArea(int[] heights) {
            int n = heights.length;
            int[] left = new int[n];
            int[] right = new int[n];

            Stack<Integer> stack = new Stack<Integer>();
            for (int i = 0; i < n; i++) {
                while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                    stack.pop();
                }
                left[i] = (stack.isEmpty())?-1:stack.peek();
                stack.push(i);
            }

            stack.clear();
            for (int i = n-1; i>= 0; i--) {
                while (!stack.empty() && heights[stack.peek()] >= heights[i]) {
                    stack.pop();
                }
                right[i] = (stack.isEmpty())?n: stack.peek();
                stack.push(i);
            }

            int ans = 0;
            for (int i = 0; i < n; i++) {
                ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
            }
            return ans;
        }
    }

    /**
     * 单调栈优化
     */
    class Solution2 {
        public int largestRectangleArea(int[] heights) {
            int n = heights.length;
            int[] left = new int[n];
            int[] right = new int[n];
            Arrays.fill(right, n);

            Stack<Integer> mono_stack = new Stack<Integer>();
            for (int i = 0; i < n; ++i) {
                while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                    right[mono_stack.peek()] = i;
                    mono_stack.pop();
                }
                left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
                mono_stack.push(i);
            }

            int ans = 0;
            for (int i = 0; i < n; ++i) {
                ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
            }
            return ans;
        }
    }
//
//    作者：LeetCode-Solution
//    链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/zhu-zhuang-tu-zhong-zui-da-de-ju-xing-by-leetcode-/
//    来源：力扣（LeetCode）
//    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.largestRectangleArea(new int[]{4,2,0,3,2,4,3,4}));
    }
}
